A Merkle tree is a tree data structure, in which nodes are labeled with checksums, e.g., hash values, of the labels or values of their child nodes. Merkle trees are used, for example, in various data storage systems for efficient data storage management.
For example, U.S. Pat. No. 8,706,701, whose disclosure is incorporated herein by reference, describes an authenticated file system that provides integrity and freshness of both data and metadata. Example embodiments rely on a balanced, Merkle-tree-based data structure that authenticates the file system directory tree and supports updates caused by file system operations.
As another example, U.S. Patent Application Publication 2016/0110261, whose disclosure is incorporated herein by reference, describes cloud storage schemes using Merkle trees. Exemplary methods include storing a data stream on a client side de-duplicating block store of a client device, generating a data stream Merkle tree of the data stream, storing a secure hash algorithm key for the data stream Merkle tree, as well as the data stream Merkle tree on the client side de-duplicating block store, recursively iterating through the data stream Merkle tree using an index of a snapshot Merkle tree of the client device that is stored on a cloud data center to determine missing Merkle nodes or missing data blocks which are present in the data stream Merkle tree but not present in the snapshot Merkle tree stored on the cloud data center, and transmitting the missing data blocks to the cloud data center.